/*
 * @Author: your name
 * @Date: 2024-04-26 10:55:54
 * @LastEditTime: 2024-04-26 12:35:02
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\105.从前序与中序遍历序列构造二叉树.cpp
 */
/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* traversal (vector<int>& preorder, int preBegin, int preEnd, vector<int>& inorder, int inBegin, int inEnd) {
        

        // 边界判断
        if(preBegin > preEnd) return nullptr;
        // 获取前序数组的第一个值,是当前数组的根节点
        int val = preorder[preBegin];
        TreeNode* root = new TreeNode(val);
        // 只有一个根节点，没有孩子节点
        if(preBegin == preEnd){
            return root;
        }

        // 在中序数组中寻找根节点的位置, 存储在site中
        int site = inBegin;
        for(; site <= inEnd; site++){
            if(inorder[site] == val) break;
        }

        // 分割中序数组
        int leftInBegin = inBegin;
        int leftInEnd = site-1;
        int rightInBegin = site+1;
        int rightInEnd = inEnd;

        // 分割前序数组
        int leftPreBegin = preBegin + 1;
        int leftPreEnd = preBegin + leftInEnd - leftInBegin + 1;
        int rightPreBegin = leftPreEnd + 1;
        int rightPreEnd = preEnd;
        // cout<<"inorder:[" <<leftInBegin <<","<< leftInEnd <<"], ["<< rightInBegin<<","<<rightInEnd<<"]"<<endl;
        // cout<<"preorder:[" <<leftPreBegin <<","<< leftPreEnd <<"], ["<< rightPreBegin<<","<<rightPreEnd<<"]"<<endl;
        root->left = traversal(preorder, leftPreBegin, leftPreEnd, inorder, leftInBegin, leftInEnd);
        root->right = traversal(preorder, rightPreBegin, rightPreEnd, inorder, rightInBegin, rightInEnd);
        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0){
            return nullptr;
        }
        return traversal(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size()-1);
    }
};
// @lc code=end

